package datastructures;

/**
 * （没有重复值的二叉树）
 * 二叉查找树的查找、插入操作、最大节点和最小节点
 */
public class BinaryTree {

    private Node tree;

    public void insert(int data) {
        if (tree == null) {
            tree = new Node(data);
            return;
        }
        Node p = tree;
        while (true) {
            if (data > p.data) {
                if (p.right == null) {
                    p.right = new Node(data);
                    return;
                }
                p = p.right;
            } else { // data < p.data
                if (p.left == null) {
                    p.left = new Node(data);
                    return;
                }
                p = p.left;
            }
        }
    }

    public void delete(int data) {
        Node p = tree;//data 所在的节点
        Node pp = null; //记录的是 p 的父节点

        while (p != null && p.data != data) {
            pp = p;
            if (data < p.data) {
                p = p.left;
            } else {
                p = p.right;
            }
        }

        if (p == null) return;//没有找到，直接返回

        /*
第一种情况是，如果要删除的p节点没有子节点
-- 我们只需要直接将父节点中，指向要删除节点的指针置为 null
第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点）
-- 我们只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了
第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了
-- 我们需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。
然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），
所以，我们可以应用上面两条规则来删除这个最小节点
         */

        //第一步处理 第三种情况两个子节点
        //找到将要把P替换的Node minp(分析可以得知P右边树下 最小节点minp：是没有子节点，或只有一个节点右节点的，所以才是最小节点)
        if (p.left != null && p.right != null) {
            //P右边的最小节点
            Node minp = p.right;
            //P右边的最小节点的父节点
            Node minpp = p;
            while (minp != null) {
                minpp = minp;
                minp = minp.left;
            }
            p.data = minp.data; //此处将 minP 的数据替换到 p 中
            p = minp; // 然后 minp 赋值给p引用变量， 下面就变成了删除 minP 了，minP等价于 p只有一个或没有子节点的情况
            pp = minpp; // 同理 minpp 赋值给p的父节点引用变量，下面就变成了删除 p的时候，就可以正确的处理父节点与子节点的连接
        }

        //第二步处理，P下有两个节点的情况，需要注意上一步中p = minp的理解
        //现在 要处理:
        // 1.p节点没有子节点
        // 2.P节点只有一个子节点
        // 3.（P下有两个节点的情况，P已经处理了，minp的值已经给P了）将minp删除，就是P，（上一步P = minp,这里是一个取巧的办法
        //而最小节点minp：是没有子节点，或只有一个节点右节点的）
        //总之 就是将p删除
        //
        //删除节点是叶子节点或者仅有一个子节点的操作，等价于  将其父节点 和 其子节点重新连接，达到删除操作
        //1.先找到 其子节点
        Node child;
        if (p.left == null) {
            child = p.right;
        } else if (p.right == null) {
            child = p.left;
        } else {
            child = null;
        }
        //2.然后 重新连接：父节和子节点相连(这里还是在删除节点是叶子节点或者仅有一个子节点的操作的情况下，因为第一步通过p = minp将问题转化成删除一个或没有子节点的情况)
        if (pp == null) {// 删除的是根节点
            tree = child;
        } else if (pp.left == p) {
            pp.left = child;
        } else {
            pp.right = child;
        }
    }


    public Node min() {
        if (tree == null) return null;
        Node p = tree;
        while (p.left != null) {
            p = p.left;
        }
        return p;
    }

    public Node max() {
        if (tree == null) return null;
        Node p = tree;
        while (p.right != null) {
            p = p.right;
        }
        return p;
    }

    public Node find(int data) {
        Node p = tree;
        while (p != null && p.data != data) {
            if (data < p.data) {
                p = p.left;
            } else {
                p = p.right;
            }
        }
        return p;
    }

    public static class Node {
        private int data;
        private Node left;
        private Node right;

        public Node(int data) {
            this.data = data;
        }
    }
}
